template <typename TValue>
class DefalutComparator
{
public:
	int operator()(TValue& l, TValue& r);
};

// 顺序查找
template<typename TIterator, typename TComparator>
TIterator Find(TIterator beginIt, TIterator endIt, typename TIterator::ValueType& value, TComparator compare);
// 交换两个元素的值
template<typename TIterator>
void Swap(TIterator it1, TIterator it2);
// 快速排序，需要能够随机访问的迭代器
template<typename TRandomAccessIterator, typename TComparator>
void QSort(TRandomAccessIterator beginRAIt, TRandomAccessIterator endRAIt, TComparator compare);
// 排序
template<typename TIterator, typename TComparator>
void Sort(TIterator beginIt, TIterator endIt, TComparator compare);
// 判断一个范围是否有序
template<typename TIterator, typename TComparator>
bool IsSorted(TIterator beginIt, TIterator endIt, TComparator compare);
// 将一个范围内第二次出现的重复元素放到后面，返回指向最后一个不重复元素的下一个位置的迭代器
// 不稳定，可能会改变原有不重复元素的顺序
template<typename TIterator, typename TComparator>
TIterator ExtractUnique(TIterator beginIt, TIterator endIt, TComparator compare);
// 判断两个范围是否有序，如果有序则合并
template<typename TIterator, typename TComparator>
TIterator MergeIfSorted(TIterator beginIt1, TIterator endIt1, TIterator beginIt2, TIterator endIt2, TIterator outBeginIt, TComparator compare);
// 合并两个有序的范围，将结果放到从outBeginIt开始的位置，并返回合并后的序列的最后一个元素的下一个位置的迭代器
// 需要预先为outBegin分配空间，否则结果是未定义的
// 需要保证有序，否则结果是未定义的
template<typename TIterator, typename TComparator>
TIterator Merge(TIterator beginIt1, TIterator endIt1, TIterator beginIt2, TIterator endIt2, TIterator outBeginIt, TComparator compare);

template<typename TIterator, typename TComparator>
TIterator Find(TIterator beginIt, TIterator endIt, typename TIterator::ValueType& value, TComparator compare)
{
	auto it = beginIt;
	while (it != endIt)
	{
		if (compare(value, *it) == 0)
		{
			break;
		}
		++it;
	}
	return it;
}

template<typename TIterator>
void Swap(TIterator it1, TIterator it2)
{
	typename TIterator::ValueType tempValue;
	tempValue = *it2;
	*it2 = *it1;
	*it1 = tempValue;
}

// 预计使用快速排序
template<typename TRandomAccessIterator, typename TComparator>
void QSort(TRandomAccessIterator beginRAIt, TRandomAccessIterator endRAIt, TComparator compare)
{
	
}

// 预计使用冒泡排序
template<typename TIterator, typename TComparator>
void Sort(TIterator beginIt, TIterator endIt, TComparator compare)
{
	
}

template<typename TIterator, typename TComparator>
bool IsSorted(TIterator beginIt, TIterator endIt, TComparator compare)
{
	auto fastIt = beginIt;
	if (fastIt == endIt)
	{
		return true;
	}
	++fastIt;
	auto slowIt = beginIt;
	while (fastIt != endIt)
	{
		if (compare(*slowIt, *fastIt) > 0)
		{
			return false;
		}
		++fastIt;
		++slowIt;
	}
	return true;
}

template<typename TIterator, typename TComparator>
TIterator ExtractUnique(TIterator beginIt, TIterator endIt, TComparator compare)
{
	auto uniqueEnd = endIt;

	for (auto uniqueBegin = beginIt; uniqueBegin != uniqueEnd; ++uniqueBegin)
	{
		auto it = uniqueBegin;
		++it;
		while (true)
		{
			auto repeatedIt = Find(it, uniqueEnd, *uniqueBegin, compare);
			if (repeatedIt == uniqueEnd)
			{
				break;
			}
			else
			{
				--uniqueEnd;
				Swap(uniqueEnd, repeatedIt);
				it = repeatedIt;
			}
		}
	}

	return uniqueEnd;
}

template<typename TIterator, typename TComparator>
TIterator MergeIfSorted(TIterator beginIt1, TIterator endIt1, TIterator beginIt2, TIterator endIt2, TIterator outBeginIt, TComparator compare)
{
	auto outEndIt = outBeginIt;
	if (!IsSorted(beginIt1, endIt1) || !IsSorted(beginIt2, endIt2))
	{
		return outEndIt;
	}
	outEndIt = Merge(beginIt1, endIt1, beginIt2, endIt2, outBeginIt, compare);
	return outEndIt;
}

template<typename TIterator, typename TComparator>
TIterator Merge(TIterator beginIt1, TIterator endIt1, TIterator beginIt2, TIterator endIt2, TIterator outBeginIt, TComparator compare)
{
	auto outIt = outBeginIt;
	auto inIt1 = beginIt1;
	auto inIt2 = beginIt2;
	while (inIt1 != endIt1)
	{
		if (inIt2 == endIt2)
		{
			do
			{
				*outIt = *inIt1;
				++outIt;
				++inIt1;
			} while (inIt1 != endIt1);
			break;
		}
		if (compare(*inIt1, *inIt2) <= 0)
		{
			*outIt = *inIt1;
			++outIt;
			++inIt1;
		}
		else
		{
			*outIt = *inIt2;
			++outIt;
			++inIt2;
		}
	}
	while (inIt2 != endIt2)
	{
		*outIt = *inIt2;
		++outIt;
		++inIt2;
	}
	return outIt;
}

template<typename TValue>
int DefalutComparator<TValue>::operator()(TValue& l, TValue& r)
{
	if (l == r)
	{
		return 0;
	}
	else if(l < r)
	{
		return -1;
	}
	else
	{
		return 1;
	}
}
